public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Main {
    public static void main(String[] args) {
        // 创建链表 [1, 4, 5]
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(5);

        // 创建链表 [1, 3, 4]
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);

        // 创建链表 [2, 6]
        ListNode l3 = new ListNode(2);
        l3.next = new ListNode(6);

        // 将链表放入数组中
        ListNode[] lists = new ListNode[] {l1, l2, l3};

//        // 打印链表以验证
//        for (ListNode list : lists) {
//            while (list != null) {
//                System.out.print(list.val + " -> ");
//                list = list.next;
//            }
//            System.out.println("null");
//        }
        mergeKLists(lists);

    }


    public static ListNode mergeKLists(ListNode[] lists) {
        // 将k个链表的合并顺序按照一个一个的
        ListNode tmp = null;
        for (int i = 0; i < lists.length; i++) {
            tmp = mergeTwoLists(tmp, lists[i]);
        }
        return tmp;
    }


    // 合并两个有序链表
    private static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 处理特殊情况
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode newHead = new ListNode(-1);
        ListNode cur1 = l1, cur2 = l2, cur = newHead;
        // 处理两个链表都不为空的情况
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                cur.next = cur1;
                cur1 = cur1.next;
            } else {
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        // 处理一个链表不为空的情况
        if (cur1 != null) {
            cur.next = cur1;
        }
        if (cur2 != null) {
            cur.next = cur2;
        }
        return newHead.next;
    }
}